package leetcode.code0818;

import java.util.Arrays;
import java.util.PriorityQueue;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {
	
	class Node {
	    int steps, target;

	    Node(int s, int t) {
	        steps = s;
	        target = t;
	    }
	}
	
    public int racecar(int target) {
//        int K = 33 - Integer.numberOfLeadingZeros(target - 1);
//        int barrier = 1 << K;
//        int[] dist = new int[2 * barrier + 1];
    	int K = Integer.toBinaryString(target).length();
    	int barrier = 1 << K;
    	int[] dist = new int[barrier + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[target] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<Node>((a, b) -> a.steps - b.steps);
        pq.offer(new Node(0, target));

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int steps = node.steps, targ1 = node.target;
            if (dist[Math.floorMod(targ1, dist.length)] > steps)
                continue;

            for (int k = 0; k <= K; ++k) {
                int walk = (1 << k) - 1;
                int targ2 = walk - targ1;
                int steps2 = steps + k + (targ2 != 0 ? 1 : 0);

                if (Math.abs(targ2) <= barrier && steps2 < dist[Math.floorMod(targ2, dist.length)]) {
                    pq.offer(new Node(steps2, targ2));
                    dist[Math.floorMod(targ2, dist.length)] = steps2;
                }
            }
        }

        return dist[0];
    }

	@Override
	public void debug4() {
		H.compare(7, this.racecar(5));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		System.out.println(Math.ceil(1.5));;
		System.out.println(Math.log(8)/Math.log(2));;
		
	}

}

